package com.zwj.interview.链表;

/**
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点
 */
public class 反转链表 {

    /**
     * 在调整节点j的next指针时，除了需要知道节点j本身，还需要知道节点j的前一个节点i，
     * 这是因为需要把节点j的next指针指向节点i。同时，还需要事先保存节点j的下一个节点k，
     * 以防止链表断开。因此，在遍历链表逐个反转每个节点的next指针时需要用到3个指针，
     * 分别指向当前遍历到的节点、它的前一个节点及后一个节点
     *
     * @param head
     * @return
     * 重点是前一种方法
     */
    public ListNode reverseList(ListNode head) {
        //1、变量prev指向当前节点的前一个节点
        ListNode prev = null;
        //2、变量cur指向当前遍历到的节点
        ListNode cur = head;
        while (cur != null) {
            //3、变量next指向当前节点的下一个节点
            ListNode next = cur.next;
            //真正执行反转
            cur.next = prev;
            //prev和cur同时向后移动指针
            prev = cur;
            cur = next;
        }
        return prev;
    }




    /**
     * 反转[a,b)区间中的节点
     * @param a
     * @param b
     * @return
     */
    public ListNode reverseListInScope(ListNode a,ListNode b) {
        //1、变量prev指向当前节点的前一个节点
        ListNode prev = null;
        //2、变量cur指向当前遍历到的节点
        ListNode cur = a;
        while (cur!=b) {
            //3、变量next指向当前节点的下一个节点，先保存下一个要反转的链表
            ListNode next = cur.next;
            //真正执行反转
            cur.next = prev;
            //prev和cur同时向后移动指针
            prev = cur;
            cur = next;

        }
        return prev;
    }
    /**    head
     *     1-->2-->3--4-->5-->6-->null
     *
     *     head
     *     1-->reverse(2-->3--4-->5-->6-->null)
     *
     *     head                last
     *     1-->2<--3<--4<-->5<--6
     *          |
     *          |
     *         null
     *
     *       head.next.next=head:
     *         head                last
     *         1-->
     *          <--2<--3<--4<-->5<--6
     *             |
     *             |
     *            null
     *
     *        head.next=null:
     *
     *       null<--1<--2<--3<--4<-->5<--6
     *
     */
    public ListNode reverse(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        ListNode last=reverse(head.next);
        head.next.next=head;
        //翻转后的head
        head.next=null;
        return last;
    }
}
